package leetcodev1.数组;

//滑动窗口
public class Solution4 {

    //暴力解
    public int minSubArrayLen1(int target, int[] nums) {
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            int j = i;
            while (j < nums.length) {
                sum += nums[j];
                if (sum >= target) {
                    ret = Math.min(ret, j - i + 1);
                    break;
                }
                j++;
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    public int minSubArrayLen2(int target, int[] nums) {
        int sum = 0, left = 0, right = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum < target) {
            return 0;
        }

        while (left <= right) {
            if (sum <= target) {
                break;
            }

            if (nums[left] < nums[right]) {
                sum -= nums[left];
                left++;
            } else if (nums[left] > nums[right]) {
                sum -= nums[right];
                right--;
            } else {
                if (nums[left + 1] > nums[right - 1]) {
                    sum -= nums[left];
                    left++;
                } else {
                    sum -= nums[right];
                    right--;
                }
            }
        }
        return right - left + 1;
    }

    //定义一个滑动窗口
    public int minSubArrayLen3(int target, int[] nums) {
        int i = 0, j = -1, sum = 0, ret = nums.length + 1;
        while (i < nums.length - 1) {
            if (j + 1 < nums.length && sum < target) {
                j++;
                sum += nums[j];
            } else {
                sum -= nums[i++];
            }

            if (sum >= target) {
                ret = Math.min(ret, j - i + 1);
            }
        }
        if (ret == nums.length + 1) {
            return 0;
        }
        return ret;
    }
}
